package Alibaba;

import common.ListNode;

/**
 * @author zhangmin
 * @create 2022-01-28 12:08
 *
 * 25. K 个一组翻转链表
 * 给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。
 * k 是一个正整数，它的值小于或等于链表的长度。
 * 如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。
 */
public class reverseKGroup25 {

    //递归翻转[a,b)之间的节点
    ListNode reverse(ListNode a,ListNode b){
        ListNode cur=a,next=a,pre=null;
        while (cur!=b){
            next=cur.next;
            cur.next=pre;
            pre=cur;
            cur=next;
        }
        return pre;
    }

    public ListNode reverseKGroup(ListNode head, int k) {
        if (head==null) return null;
        ListNode a=head,b=head;//用于区间内翻转
        for (int i = 0; i < k; i++) {
            if (b==null) return head;//不足k个不需要翻转
            b=b.next;
        }
        ListNode newhead = reverse(a, b);
        //翻转完成后a是最后一个元素,b是还没翻转的头结点
        a.next=reverseKGroup(b,k);
        return newhead;
    }
}
